package com.duing.array;


import java.util.*;

public class RepeatNumber1 {

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 2, 5, 3};
//        System.out.println(findDuplicates(arr));
//        System.out.println(findDuplicates1(arr));
//        System.out.println(findDuplicates2(arr));
        System.out.println(findDuplicates3(arr));
    }

    public static int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }

    public static List<Integer> findDuplicates(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i]) && !list.contains(nums[i])) {
                list.add(nums[i]);
            }
            set.add(nums[i]);
        }
        return list;
    }

    public static List<Integer> findDuplicates1(int[] nums) {
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1] && !list.contains(nums[i])) {
                list.add(nums[i]);
            }
        }
        return list;
    }

    public static List<Integer> findDuplicates2(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int[] tmp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int index = nums[i] - 1;
            if (tmp[index] == 1) {
                list.add(nums[i]);
            }
            tmp[index]++;
        }
        return list;
    }

    public static List<Integer> findDuplicates3(int[] nums) {
        List<Integer> list = new ArrayList<>();
        // 交换位置
        for (int i = 0; i < nums.length; i++) {

            // 如果索引正好等于元素本身  是期望的结果  跳过
            if (nums[i] == i) continue;

            // i = 0
            int num = nums[i]; // 2
            // 如果要交换的位置  已经有期望值  说明重复
            if (nums[num] == num) {
//                System.out.println("当前索引为" + num + "的位置 已经有" + num + "值，重复了");
                if (!list.contains(num)) {
                    list.add(num);
                }
                continue;
            }
            int tmp = nums[num]; // 1
            nums[num] = num;
            nums[i] = tmp;
            // [1, 3, 2, 0, 2, 5, 3]
            // 交换仍需遍历当前位置的值  所以抵消i++
            i--;
//            System.out.println(Arrays.toString(nums));
        }
        return list;
    }

}
